import java.util.ArrayList;

public class GetCoins {
    public int getCoins (ArrayList<Integer> coins) {
        // write code here
        // dp[i][j]表示区间[i,j]之间的金币都取的最高积分
        // dp[i][j] = dp[i][k-1]+dp[k+1][j]+coins[k]*coins[i-1]*coins[j+1]
        // 因为会用到i-1、i+1、j-1、j+1行和列的数据，所以为了避免出界，多创建两行和两列
        int len = coins.size();
        int[] arr = new int[len+2];
        arr[0] = arr[len+1] = 1;
        for (int i = 1; i <= len; i++) {
            arr[i] = coins.get(i-1);
        }
        int[][] dp = new int[len+2][len+2];
        // 填表顺序是从下往上，从左往右
        for (int i = len; i >= 1; i--) {
            for (int j = i ; j <= len; j++) {
                for (int k = i; k <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][k-1]+dp[k+1][j]+arr[i-1]*arr[k]*arr[j+1]);
                }
            }
        }
        return dp[1][len];
    }

    public static void main(String[] args) {
        GetCoins getCoins = new GetCoins();
        System.out.println(getCoins.getCoins(new ArrayList<Integer>(){{
            add(5);
            add(6);
            add(4);
            add(8);
        }}));
    }
}
